package com.yan_jiu_sheng.LeetCodeHot100.AC;

/**
 * https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-100-liked
 * 非原地方法通过
 *
 * @author yulongTian
 * @create 2024-06-15 15:34
 */
public class Test46 {
    public static void main(String[] args) {
        TreeNode root1 = new Test46().new TreeNode(1);
        TreeNode root2 = new Test46().new TreeNode(2);
        TreeNode root3 = new Test46().new TreeNode(3);
        TreeNode root4 = new Test46().new TreeNode(4);
        TreeNode root5 = new Test46().new TreeNode(5);
        TreeNode root6 = new Test46().new TreeNode(6);
        root1.left = root2;
        root1.right = root5;
        root2.left = root3;
        root2.right = root4;
        root5.right = root6;
        new Test46().flatten(root1);

    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 尝试原地方法
     * 参考题解：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solutions/17274/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26
     *
     * @param root
     */
    public void flatten(TreeNode root) {
        while (root != null) {
            //左子树为 null，直接考虑下一个节点
            if (root.left == null) {
                root = root.right;
            } else {
                // 找左子树最右边的节点
                TreeNode pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                //将原来的右子树接到左子树的最右边节点
                pre.right = root.right;
                // 将左子树插入到右子树的地方
                root.right = root.left;
                root.left = null;
                // 考虑下一个节点
                root = root.right;
            }
        }
    }

//    /**
//     * 非原地方法
//     *
//     * @param root
//     */
//    public void flatten(TreeNode root) {
//        List<TreeNode> list = new LinkedList<>();
//        preOrderTravel(root, list);
//        TreeNode p = root;
//        for (int i = 1; i < list.size(); i++) {
//            p.left = null;
//            p.right = list.get(i);
//            p = list.get(i);
//        }
//    }
//
//    public void preOrderTravel(TreeNode root, List<TreeNode> list) {
//        if (root == null) {
//            return;
//        }
//        // 根
////        System.out.println(root.val);
//        list.add(root);
//        // 左
//        preOrderTravel(root.left, list);
//        // 右
//        preOrderTravel(root.right, list);
//
//    }

}
